/**
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 * 柱状图的最大矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * @param heights
 */
export const largestRectangleArea = (heights: number[]): number => {
  // 寻找左右的最小值
  const len = heights.length;

  // 默认为-1, 默认是这个柱状图左边没有比它小的
  const left = new Array(len).fill(-1);

  //! right 默认为柱状图的长度, 方便计算最大矩形面积
  const right = new Array(len).fill(len);

  const stack: number[] = [];

  for (let i = 0; i < len; i++) {
    // 栈不为空并且栈顶大于当前的柱状图的高度, 那么该高度就是栈中的顶的右边的第一个比它小的
    while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
      right[stack.pop()!] = i;
    }

    // 栈不为空, 此时栈顶就是当前柱子的高度左边的第一个比它小的
    if (stack.length) {
      left[i] = stack[stack.length - 1];
    }

    // 将该值的索引放入栈中
    stack.push(i);
  }

  let ans = 0
  for (let i = 0; i < len; i++) {
    ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
  }

  return ans;
};

// console.log(largestRectangleArea([2, 1, 5, 6, 2, 3]));
console.log(largestRectangleArea([2, 4]));
